package com.fang.恒天软件;


import java.util.*;




public class Tree {
    TreeNode head;

    public Tree(TreeNode node) {
        this.head = node;
    }


    class ForeachNoMethodException extends Exception {
        public ForeachNoMethodException(String message) {
            super(message);
        }
    }

    private static final String EXCEPTION_MSG = "没有该遍历方式，请从【1(深度优先前序遍历所有)、2(深度优先前序遍历奇数)、3(深度优先前序遍历偶数)、" +
            "4(深度优先后序遍历所有)、5(深度优先后序遍历奇数)、6(深度优先后序遍历偶数)】";

    /**
     * 默认不传走顺序遍历
     */
    public void foreach() {
        foreach(ForEachMethod.orderFrontMethod);
    }

    public void foreach(ForEachMethod method) {
        ForEachFactory factory = new ForEachFactory();
        print(factory.getForEachWay(method).execute());
    }

    private void print(List<Integer> list) {
        list.forEach(val -> {
            if (list.indexOf(val) == list.size() - 1) {
                System.out.print(val);
            } else {
                System.out.print(val + " ");
            }
        });
    }



    class ForEachFactory {
        Map<Tree.ForEachMethod, Tree.ForEachWay> forEachWayMap = new HashMap<>(16, 0.75F);

        public ForEachFactory() {
            registerForEachWay(ForEachMethod.orderFrontMethod, new FrontForEach(ForEachMethod.orderFrontMethod));
            registerForEachWay(ForEachMethod.oddFrontMethod, new FrontForEach(ForEachMethod.oddFrontMethod));
            registerForEachWay(ForEachMethod.evenFrontMethod, new FrontForEach(ForEachMethod.evenFrontMethod));
            registerForEachWay(ForEachMethod.orderBackMethod, new BackForEach(ForEachMethod.orderBackMethod));
            registerForEachWay(ForEachMethod.oddBackMethod, new BackForEach(ForEachMethod.oddBackMethod));
            registerForEachWay(ForEachMethod.evenBackMethod, new BackForEach(ForEachMethod.evenBackMethod));
        }

        private void registerForEachWay(Tree.ForEachMethod method, Tree.ForEachWay way) {
            forEachWayMap.put(method, way);
        }

        public Tree.ForEachWay getForEachWay(ForEachMethod method)  {
            try {
                if (forEachWayMap.containsKey(method)) {
                    return forEachWayMap.get(method);
                } else {
                    throw new ForeachNoMethodException(EXCEPTION_MSG);
                }
            } catch (ForeachNoMethodException e) {

            }
            return null;
        }
    }

    interface ForEachWay {
        List<Integer> execute();
    }

    class FrontForEach implements ForEachWay {

        ForEachMethod method;

        public FrontForEach(ForEachMethod method) {
            this.method = method;
        }

        @Override
        public List<Integer> execute() {
            List<Integer> result = new ArrayList<>();
            if (Objects.isNull(head)) {
                return result;
            }
            Stack<TreeNode> stack = new Stack<>();
            stack.push(head);
            while (!stack.empty()) {
                TreeNode node = stack.pop();
                if (Objects.equals(method, ForEachMethod.orderFrontMethod)) {
                    result.add(node.value);
                } else if (Objects.equals(method, ForEachMethod.oddFrontMethod) && node.value % 2 != 0) {
                    result.add(node.value);
                } else if (Objects.equals(method, ForEachMethod.evenFrontMethod) && node.value % 2 == 0) {
                    result.add(node.value);
                }
                for (int i = node.nodes.size() - 1; i >= 0; i--) {
                    stack.push(node.nodes.get(i));
                }
            }
            return result;
        }
    }




    class BackForEach implements ForEachWay {

        ForEachMethod method;

        public BackForEach(ForEachMethod method) {
            this.method = method;
        }

        @Override
        public List<Integer> execute() {
            List<Integer> result = new ArrayList<>();
            if (Objects.isNull(head)) {
                return result;
            }
            Stack<TreeNode> stack = new Stack<>();
            stack.push(head);

            while (!stack.isEmpty()) {
                TreeNode cur = stack.pop();
                if (Objects.equals(method, ForEachMethod.orderBackMethod)) {
                    result.add(cur.value);
                } else if (Objects.equals(method, ForEachMethod.oddBackMethod) && cur.value % 2 != 0) {
                    result.add(cur.value);
                } else if (Objects.equals(method, ForEachMethod.evenBackMethod) && cur.value % 2 == 0) {
                    result.add(cur.value);
                }

                for (TreeNode node : cur.nodes) {
                    stack.push(node);
                }
            }
            Collections.reverse(result);
            return result;
        }
    }



    /**
     * 非二叉树的节点
     */
    static class TreeNode {
        Integer value;
        List<TreeNode> nodes;

        public TreeNode(Integer value, List<TreeNode> nodes) {
            this.value = value;
            this.nodes = nodes;
        }

        public TreeNode(Integer value) {
            this.value = value;
            this.nodes = new ArrayList<>();
        }
    }

    /**
     * 打印节点方式
     */
    enum ForEachMethod {
        // 根 -> 左 -> 右
        orderFrontMethod("1", "深度优先前序遍历所有"),
        oddFrontMethod("2", "深度优先前序遍历奇数"),
        evenFrontMethod("3", "深度优先前序遍历偶数"),

        // 左 右 根
        orderBackMethod("4", "深度优先后序遍历所有"),
        oddBackMethod("5", "深度优先后序遍历奇数"),
        evenBackMethod("6", "深度优先后序遍历偶数")
        ;

        final String value;
        final String name;

        ForEachMethod(String value, String name) {
            this.value = value;
            this.name = name;
        }
    }

}

class Demo {
    public static void main(String[] args)  {
        List<Tree.TreeNode> treeNodes = new ArrayList<>();

        /**
         *              1
         *           /  |  \
         *        2     3      4
         *      / | \  / \    / \
         *     5  6 7 8   9  10  11
         */
        Tree.TreeNode node5 = new Tree.TreeNode(5);
        Tree.TreeNode node6 = new Tree.TreeNode(6);
        Tree.TreeNode node7 = new Tree.TreeNode(7);
        Tree.TreeNode node2 = new Tree.TreeNode(2, Arrays.asList(node5, node6, node7));

        Tree.TreeNode node8 = new Tree.TreeNode(8);
        Tree.TreeNode node9 = new Tree.TreeNode(9);
        Tree.TreeNode node3 = new Tree.TreeNode(3, Arrays.asList(node8, node9));


        Tree.TreeNode node10 = new Tree.TreeNode(10);
        Tree.TreeNode node11 = new Tree.TreeNode(11);
        Tree.TreeNode node4 = new Tree.TreeNode(4, Arrays.asList(node10, node11));

        Tree.TreeNode head = new Tree.TreeNode(1, Arrays.asList(node2, node3, node4));


        Tree tree = new Tree(head);


        tree.foreach(Tree.ForEachMethod.orderFrontMethod); // 1 2 5 6 7 3 8 9 4 10 11
        System.out.println();
        tree.foreach(Tree.ForEachMethod.oddFrontMethod); // 1 5 7 3 9 11
        System.out.println();
        tree.foreach(Tree.ForEachMethod.evenFrontMethod); // 2 6 8 4 10


        System.out.println("\n-----------------------------------------");
        tree.foreach(Tree.ForEachMethod.orderBackMethod); // 5 6 7 2 8 9 3 10 11 4 1
        System.out.println();
        tree.foreach(Tree.ForEachMethod.oddBackMethod); // 5 7 9 3 11 1
        System.out.println();
        tree.foreach(Tree.ForEachMethod.evenBackMethod); // 6 2 8 10 4
    }
}
